package com.czh.problem.likou;

import java.util.*;

/**
 * 力扣刷题
 *
 * @author chenzhihua
 * @Date 2024/2/26
 */
public class SolutionLikou {
    public static void main(String[] args) {
        SolutionLikou solutionLikou = new SolutionLikou();
        // 70. 爬楼梯---满足斐波那契数 1=1 2=2 f(n)=f(n-1)+f(n-2)
        // 1,2,3,5,89
//        System.out.println(solutionLikou.climbStairs(1));
//        System.out.println(solutionLikou.climbStairs(2));
//        System.out.println(solutionLikou.climbStairs(3));
//        System.out.println(solutionLikou.climbStairs(4));
//        System.out.println(solutionLikou.climbStairs(10));
        // 1. 两数之和
//        System.out.println(Arrays.toString(solutionLikou.twoSum(new int[]{2, 7, 11, 15}, 9)));
        // 88. 合并两个有序数组 小->大
//        int[] nums1 = {1, 2, 3, 0, 0, 0};
//        int[] nums2 = {2, 5, 6};
//        int[] nums1 = {4, 0, 0, 0, 0, 0};
//        int[] nums2 = {1, 2, 3, 5, 6};
//        solutionLikou.merge(nums0, 0, nums4, 1);
//        solutionLikou.merge(nums1, 1, nums2, 5);
        //283. 移动零
//        int[] nums1 = {0,1,0,3,12};
//        int[] nums1 = {0};
//        solutionLikou.moveZeroes(nums1);
        // 448. 找到所有数组中消失的数字
//        int[] nums1 = {4, 3, 2, 7, 8, 2, 3, 1};
//        int[] nums1 = {1, 1};
//        List<Integer> disappearedNumbers = solutionLikou.findDisappearedNumbers(nums1);
//        System.out.println(disappearedNumbers);
        //21. 合并两个有序链表
//        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(2);
//        ListNode l3 = new ListNode(4);
//        l1.next = l2;
//        l2.next = l3;
//        ListNode l11 = new ListNode(1);
//        ListNode l21 = new ListNode(3);
//        ListNode l31 = new ListNode(4);
//        l11.next = l21;
//        l21.next = l31;
//        ListNode listNode = solutionLikou.mergeTwoLists(l1, l11);

        //83. 删除排序链表中的重复元素
//        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(1);
//        ListNode l3 = new ListNode(2);
//        ListNode l4 = new ListNode(4);
//        ListNode l5 = new ListNode(4);
//        l1.next = l2;
//        l2.next = l3;
//        l3.next = l4;
//        l4.next = l5;
//        ListNode listNode = solutionLikou.deleteDuplicates(l1);
        //141. 环形链表
//        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(1);
//        ListNode l3 = new ListNode(2);
//        ListNode l4 = new ListNode(4);
//        ListNode l5 = new ListNode(4);
//        l1.next = l2;
//        l2.next = l3;
//        l3.next = l4;
//        l4.next = l2;
//        System.out.println(solutionLikou.hasCycle(l1));
        //142. 环形链表 II
//        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(1);
//        ListNode l3 = new ListNode(2);
//        ListNode l4 = new ListNode(4);
//        ListNode l5 = new ListNode(4);
//        l1.next = l2;
//        l2.next = l3;
//        l3.next = l4;
//        l4.next = l2;
//        System.out.println(solutionLikou.detectCycle(l1));
        //160. 相交链表
//        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(2);
//        ListNode l3 = new ListNode(4);
//        l1.next = l2;
//        l2.next = l3;
//        ListNode l11 = new ListNode(1);
//        ListNode l21 = new ListNode(3);
//        ListNode l31 = new ListNode(4);
//        l11.next = l21;
//        l21.next = l31;
//        solutionLikou.getIntersectionNode(l1, l11);
        //206. 反转链表
//        ListNode l11 = new ListNode(1);
//        ListNode l21 = new ListNode(3);
//        ListNode l31 = new ListNode(4);
//        l11.next = l21;
//        l21.next = l31;
//        ListNode listNode = solutionLikou.reverseList(l11);
        //234. 回文链表
//        ListNode node1 = new ListNode(1);
//        ListNode node2 = new ListNode(2);
////        ListNode node3 = new ListNode(3);
//        ListNode node4 = new ListNode(2);
//        ListNode node5 = new ListNode(1);
//        node1.next = node2;
//        node2.next = node4;
////        node2.next = node3;
////        node3.next = node4;
//        node4.next = node5;
//        System.out.println(solutionLikou.isPalindrome(node1));
        //876. 链表的中间结点
        //链表中倒数第k个节点
//        ListNode node1 = new ListNode(1);
//        ListNode node2 = new ListNode(2);
//        ListNode node3 = new ListNode(3);
//        ListNode node4 = new ListNode(4);
//        ListNode node5 = new ListNode(5);
//        ListNode node6 = new ListNode(6);
//        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
//        node4.next = node5;
//        node5.next = node6;
//        ListNode listNode = solutionLikou.FindKthToTail(node1, 3);
//        System.out.println(listNode.val);
//        System.out.println(Arrays.toString(nums1));
        // 232. 用栈实现队列
//        MyQueue myQueue = new MyQueue();
        // 394. 字符串解码
//        String s = "2[abc]3[cd]ef";
//        System.out.println(solutionLikou.decodeString(s));
        // 94. 二叉树的中序遍历
//        TreeNode treeNode1 = new TreeNode(1);
//        TreeNode treeNode2 = new TreeNode(2);
//        TreeNode treeNode3 = new TreeNode(2);
//        treeNode1.right = treeNode2;
//        treeNode1.left = treeNode3;
//        System.out.println(solutionLikou.inorderTraversal(new TreeNode()));
        //144. 二叉树的前序遍历
//        System.out.println(solutionLikou.preorderTraversal(treeNode1));
        //101. 对称二叉树
//        System.out.println(solutionLikou.isSymmetric(treeNode1));
        // // 104. 二叉树的最大深度
//        System.out.println(solutionLikou.maxDepth(treeNode1));
        // 110. 平衡二叉树
//        System.out.println(solutionLikou.isBalanced(treeNode1));

//        int[] nums1 = {81, 2, 3, 5, 2, 88};
//        // 冒泡排序
//        solutionLikou.bubbleSort(nums1);
//        // 选择排序
//        solutionLikou.selectSort(nums1);
//        // 插入排序
//        solutionLikou.insertSort(nums1);
//        System.out.println(Arrays.toString(nums1));

        //136. 只出现一次的数字
//        int[] nums1 = {81, 2, 3, 5, 2, 88};
//        System.out.println(solutionLikou.singleNumber(nums1));
        // 338. 比特位计数
//        System.out.println(Arrays.toString(solutionLikou.countBits(5)));
//        System.out.println(solutionLikou.isValid("()"));
//        System.out.println(solutionLikou.addStrings("111", "99"));
        // 509. 斐波那契数
//        System.out.println(solutionLikou.fib(10));
//        int[] nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
//        System.out.println(solutionLikou.maxSubArray(nums1));
//        System.out.println(solutionLikou.eratosthenes(97));
//        int[] nums1 = {0, 1, 2, 2, 3, 3, 4};
//        System.out.println(solutionLikou.removeDuplicates(nums1));
//        int[] nums1 = {1, 7, 3, 6, 5, 6};
//        System.out.println(solutionLikou.pivotIndex(nums1));
        System.out.println(solutionLikou.binarySearchOrNewton(2147395599));
    }

    //========================递归====================================//
    // 70. 爬楼梯---满足斐波那契数 1=1 2=2 f(n)=f(n-1)+f(n-2)
    // 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    // 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
    private Map<Integer, Integer> map = new HashMap<>();

    public int climbStairs(int n) {
        //1.递归实现，但是时间复杂度高
//        if (n == 1 || n == 2) {
//            return n;
//        }
//        return climbStairs(n - 1) + climbStairs(n - 2);
        //2.hash+递归实现
//        if (n == 1 || n == 2) {
//            return n;
//        }
//        if (map.get(n) != null) {
//            return map.get(n);
//        } else {
//            int result = climbStairs(n - 1) + climbStairs(n - 2);
//            map.put(n, result);
//            return result;
//        }

        //3.动态规划
        if (n == 1 || n == 2) {
            return n;
        }
        int sum = 0;
        int prepre = 1; // 当前值的上上值
        int pre = 2;  // 当前值的上值
        for (int i = 3; i <= n; i++) {
            sum = pre + prepre;
            prepre = pre;
            pre = sum;
        }
        return sum;
    }


    //========================数组====================================//
    // 1. 两数之和
    public int[] twoSum(int[] nums, int target) {
        // 1. 暴力遍历法
//        int[] result = new int[2];
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = 0; j < nums.length; j++) {
//                if (nums[i] + nums[j] == target) {
//                    result[0] = i;
//                    result[1] = j;
//                    return result;
//                }
//            }
//        }
        //2.hash存储，key:target-当前值 , value: 当前值的下标
        for (int i = 0; i < nums.length; i++) {
            if (map.get(nums[i]) == null) {
                map.put(target - nums[i], i);
            } else {
                return new int[]{map.get(nums[i]), i};
            }
        }
        return null;
    }

    //88. 合并两个有序数组 小->大
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // JDK自带
//        for (int i = 0; i < n; i++) {
//            nums1[m] = nums2[i];
//        }
//        Arrays.sort(nums1);
        // 双指针实现(效率低顺序处理)
        if (n == 0) {
            return;
        }
        if (m == 0) {
            for (int i = 0; i < n; i++) {
                nums1[i] = nums2[i];
            }
            return;
        }
//        int n1 = 0;
//        int n2 = 0;
//        while (n1 < m && n2 < n) {
//            if (nums1[n1] <= nums2[n2]) {
//                n1++;
//            } else {
//                for (int i = m - 1; i >= n1; i--) {
//                    int temp = nums1[i + 1];
//                    nums1[i + 1] = nums1[i];
//                    nums1[i] = temp;
//                }
//                nums1[n1] = nums2[n2];
//                m++;
//                n2++;
//            }
//        }
//        // 如果n2还有数据则直接赋值给n1
//        if (n2 < n) {
//            for (int i = n2; i < n; i++) {
//                nums1[n1++] = nums2[i];
//            }
//        }
        // 双指针实现(倒叙处理)
        int n1 = m - 1;
        int n2 = n - 1;
        int k = m + n - 1;
        while (n1 >= 0 && n2 >= 0) {
            if (nums1[n1] <= nums2[n2]) {
                nums1[k--] = nums2[n2--];
            } else {
                nums1[k--] = nums1[n1--];
            }
        }
        // 如果n2没到头则将所有值插入到num1前面
        while (n2 >= 0) {
            nums1[n2] = nums2[n2];
            n2--;
        }
    }

    //283. 移动零(双指针，left从头指向最后一个有效值,right从头遍历有效值然后把这个值赋值给left)
    public void moveZeroes(int[] nums) {
        int left = 0, right = 0;  // left表示非零数
        while (right < nums.length) {
            if (nums[right] != 0) {
                nums[left++] = nums[right];
            }
            right++;
        }
        for (int i = left; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    //448. 找到所有数组中消失的数字(遍历数组,将当前值的绝对值所对应的数字作为该数组的下标进行负数处理)
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int num = Math.abs(nums[i]) - 1;
            if (nums[num] > 0) {
                nums[num] = nums[num] * -1;
            }
        }
        for (int i = 1; i <= nums.length; i++) {
            if (nums[i - 1] > 0) {
                list.add(i);
            }
        }
        return list;
    }


    //========================链表====================================//
    //21. 合并两个有序链表(双指针解法)
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        // 因为头节点不确定所以需要创建一个头节点
        ListNode result = new ListNode();
        // 创建一个头指针
        ListNode head = result;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                head.next = list1;
                list1 = list1.next;
            } else {
                head.next = list2;
                list2 = list2.next;
            }
            head = head.next;
        }
        if (list1 != null) {
            head.next = list1;
        }
        if (list2 != null) {
            head.next = list2;
        }
        return result.next;
    }

    //83. 删除排序链表中的重复元素
    public ListNode deleteDuplicates(ListNode head) {
        // 防御性编程
        if (head == null) {
            return head;
        }
        ListNode result = head;
        while (result.next != null) {
            if (result.val == result.next.val) {
                if (result.next.next == null) {
                    result.next = null;
                } else {
                    result.next = result.next.next;
                }
            } else {
                result = result.next;
            }
        }
        return head;
    }

    //141. 环形链表(快慢指针,快: 走两步,慢: 一步)
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        // 定义一个快慢指针
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    //142. 环形链表 II
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        // 1. 判断环是否存在
        boolean loopExists = false;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                loopExists = true;
                break;
            }
        }
        //2.环存在的话，将慢指针重新值向头节点，然后快慢指针已相同的速度移动
        if (loopExists) {
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
        // 环不存在时
        return null;


    }

    //160. 相交链表(hash实现/先计算两个单链表的差值，然后将长的往前移动,最后进行两个值的比较)
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode lA = headA, lB = headB;
        ListNode hA = headA, hB = headB;
        // 计算链表的长度
        int lengthA = 0;
        while (lA != null) {
            lengthA++;
            lA = lA.next;
        }
        int lengthB = 0;
        while (lB != null) {
            lengthB++;
            lB = lB.next;
        }
        // 长的链表后移
        for (int i = 0; i < Math.abs(lengthB - lengthA); i++) {
            if (lengthA > lengthB) {
                hA = hA.next;
            } else {
                hB = hB.next;
            }
        }

        while (hA != null) {
            if (hA == hB) {
                return hA;
            }
            hA = hA.next;
            hB = hB.next;
        }
        return null;
    }

    //206. 反转链表
    public ListNode reverseList(ListNode head) {
        // 递归实现
        if (head == null) {
            return head;
        }
        // 递归
        if (head.next == null) {
            return head;
        }
        ListNode listNode = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return listNode;
    }

    //234. 回文链表
    public boolean isPalindrome(ListNode head) {
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        int front = 0;
        int real = list.size() - 1;
        while (front < real) {
            if (list.get(front).val != list.get(real).val) {
                return false;
            }
            front++;
            real--;
        }
        return true;
    }

    //876. 链表的中间结点(快慢指针)
    public ListNode middleNode(ListNode head) {
        // 处理一个节点或者两个节点的情况
        if (head.next == null) {
            return head;
        }
        //处理两个节点的情况
        if (head.next.next == null) {
            return head.next;
        }
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // 链表中倒数第k个节点
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k <= 0) {
            return null;
        }
        // 1. 先算出链表的长度
        int length = 0;
        ListNode node = head, result = head;
        while (node != null) {
            node = node.next;
            length++;
        }
        for (int i = k; i < length; i++) {
            result = result.next;
        }
        return result;

    }

    //========================栈和队列====================================//

    //394. 字符串解码
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<String> retStack = new Stack<>();
        int index = 0;
        String result = "";
        // 遍历字符
        while (index < s.length()) {
            char c = s.charAt(index);

            // 如果是数字
            if (Character.isDigit(c)) {
                // 如果存在大于9的数量
                StringBuffer count = new StringBuffer();
                while (Character.isDigit(s.charAt(index))) {
                    count.append(s.charAt(index++));
                }
                countStack.push(Integer.valueOf(count.toString()));
            }
            // 如果是[: 入栈，然后继续遍历
            else if (c == '[') {
                retStack.push(result);
                result = "";
                index++;
            }
            // 如果是]: 进行出栈和重复字符串然后入栈
            else if (c == ']') {
                StringBuffer tem = new StringBuffer(retStack.pop());
                Integer num = countStack.pop();
                for (int i = 0; i < num; i++) {
                    tem.append(result);
                }
                result = tem.toString();
                index++;
            }
            // 如果是其它字符: 拼接字符然后继续往下遍历
            else {
                result += s.charAt(index++);
            }
        }
        return result;
    }

    //========================树====================================//
    // 94. 二叉树的中序遍历(左根右)
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> result = new ArrayList<>();
        if (root.left != null) {
            result.addAll(inorderTraversal(root.left));
        }
        result.add(root.val);
//        System.out.println(root.val);
        if (root.right != null) {
            result.addAll(inorderTraversal(root.right));
        }
        return result;
    }

    // 144. 二叉树的前序遍历(根左右)
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> list = new ArrayList<>();
        list.add(root.val);
        if (root.left != null) {
            list.addAll(preorderTraversal(root.left));
        }
        if (root.right != null) {
            list.addAll(preorderTraversal(root.right));
        }
        return list;
    }

    //145. 二叉树的后序遍历(左右根)
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> list = new ArrayList<>();
        if (root.left != null) {
            list.addAll(postorderTraversal(root.left));
        }
        if (root.right != null) {
            list.addAll(postorderTraversal(root.right));
        }
        list.add(root.val);
        return list;

    }

    //101. 对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return deepCheck(root.left, root.right);
    }

    private boolean deepCheck(TreeNode left, TreeNode right) {
        // 终止条件是两个节点都为空、一个为空、两个节点的值不相等
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return deepCheck(left.left, right.right) && deepCheck(left.right, right.left);
    }

    // 104. 二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    // 110. 平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return processBalance(root) != -1;
    }

    private int processBalance(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = processBalance(root.left);
        int right = processBalance(root.right);
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        return Math.max(left, right) + 1;
    }

    // 226. 翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        TreeNode tem = root.left;
        root.left = root.right;
        root.right = tem;
        return root;
    }

    //========================十大排序算法 TODO 常考 推排序、归并排序、快速排序 ====================================//
    //冒泡排序
    public void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    //选择排序
    public void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    // 交换
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    //归并排序
    public void mergeSort(int[] arr) {

    }

    //推排序
    public void headSort(int[] arr) {

    }

    //快速排序
    public void quickSort(int[] arr) {
    }

    //希尔排序
    //计数排序
    //基数排序
    //桶排序
    //========================位运算操作====================================//
    //136. 只出现一次的数字
    public int singleNumber(int[] nums) {
        // 所有元素和0进行异或操作: 相同数异或为0，任何数异或0为本身
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result = result ^ nums[i];
        }
        return result;
    }

    // 338. 比特位计数
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for (int i = 1; i < result.length; i++) {
            result[i] = result[i & (i - 1)] + 1;
        }
        return result;
    }

    // 461. 汉明距离
    public int hammingDistance(int x, int y) {
        int xor = x ^ y;
        int distinct = 0;
        while (xor != 0) {
            if (xor % 2 == 1) {
                distinct++;
            }
            xor = xor >> 1;
        }
        return distinct;
    }

    //========================字符串处理====================================//
    // 20. 有效的括号
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) {
                    return false;
                }
                Character pop = stack.pop();
                if (pop != c) {
                    return false;
                }
            } else {
                return false;
            }
        }
        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }

    // 415. 字符串相加
    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        for (int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0 || carry == 1; i--, j--) {
            int x = i < 0 ? 0 : num1.charAt(i) - '0'; // 获取当前奥处理的一个字符，同时对遍历一个数完成以后容错
            int y = j < 0 ? 0 : num2.charAt(j) - '0';
            sb.append((x + y + carry) % 10);
            carry = (x + y + carry) / 10;
        }
        return sb.reverse().toString();
    }

    // 1.字符串匹配之BF算法(暴力穷举算法JDK的indexOf)
    // 2.字符串匹配之BM算法: 从需要匹配的尾部开始比较;
    // 坏字符: 坏字符的位置-模式串中的上一次出现的位置(未出现则为-1)
    // 好字符: 好后缀的位置-模式串中的上一次出现位置(未出现则为-1)
    // 3.字符串匹配之KMP算法

    //========================动态规划: 主要解决多阶段决策最优解模型====================================/
    // 509. 斐波那契数
    public int fib(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    // 53. 最大子数组和: dp数组: 包括下标i之前的最大连续子序列和
    public int maxSubArray(int[] nums) {
//        int[] dp = new int[nums.length];
//        dp[0] = nums[0];
//        int result = dp[0];
//        for (int i = 1; i < nums.length; i++) {
//            // 状态转换公式
//            dp[i] = Math.max(nums[i], (nums[i] + dp[i - 1]));
//            // result保存最大值
//            if (result < dp[i]) {
//                result = dp[i];
//            }
//        }
//        return result;
        // 优化
        int result = nums[0];
        // pre代表前面的最大序列和
        int pre = result;
        for (int i = 1; i < nums.length; i++) {
            // 比较当前值和前面的最大序列和谁大
            pre = Math.max(pre + nums[i], nums[i]);
            if (result < pre) {
                result = pre;
            }
        }
        return result;
    }

    // 121. 买卖股票的最佳时机
    public int maxProfit(int[] prices) {
        // 保存最小值
        int minPrice = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (minPrice > prices[i]) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }
    //========================其它====================================/

    // 素数个数的统计-埃筛法: 利用合数的概念，素数*n必然是合数，因此可以从2开始遍历，将所有的合数做上标记
    public int eratosthenes(int n) {
        boolean[] isPrime = new boolean[n]; // 默认全false：false代表素数
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) {
                count++;
                for (int j = i * i; j < n; j += i) {  // j就是合数的标记位
                    isPrime[j] = true;
                }
            }
        }
        return count;
    }

    // 删除排序数组中的重复项: 快慢指针
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                nums[++i] = nums[j];
            }
        }
        return i + 1;
    }

    // 寻找数组的中心下标: 左侧和等于右侧合，不存在-1，多个时返回左边第一个
    public int pivotIndex(int[] nums) {
        // 先计算总和
        int sum = Arrays.stream(nums).sum();
        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            // total左边的合
            total += nums[i];
            if (total == sum) {
                return i;
            }
            // sum右边的合
            sum -= nums[i];
        }
        return -1;
    }

    // x的平方根: 得到整数位 二分法合牛顿迭代
    public int binarySearchOrNewton(int x) {
        // 二分法logn
        int index = -1, l = 0, r = x;
        while (l <= r) {
            // 获取中间数
            int m = l + (r - l) / 2;
            if (m * m <= x) {
                index = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return index;
    }



}

// 定义一个链表
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

// 定义一个树
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

//232. 用栈实现队列
class MyQueue {
    private Stack<Integer> inStack; // 输入栈
    private Stack<Integer> outStack; // 输出栈

    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.pop();
    }

    public int peek() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void in2out() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}